/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <iostream>
using namespace std;
#include <map>
 struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
 };
class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode*, int> mp;
        ListNode * tmp = head;
        int cur = 0;
        int res = 0;
        while (tmp != NULL) {
            auto it = mp.find(tmp);
            if (it == mp.end()){
                mp[tmp] = cur;
                tmp = tmp->next;
                cur++;
            } else {
                res = mp[tmp];
                return true;
            }
        }
        return false;
    }
};